第一章作业

1.1 复习与思考题

1.1.3 三种误差

• 算法无关

  • 模型误差：数学模型与实际问题之间的误差.

  • 观测误差：物理量与观测值之间的误差.

• 算法相关

  • 截断误差（方法误差）：近似解与精确解之间的误差.

  • 舍入误差：四舍五入、进制转换的误差.

1.1.4 绝对误差、相对误差、有效数字

• 误差衡量

  • 有量纲

    • 绝对误差：$e^{\ast }=x^{\ast }-x$$e^* = x^* - x$.

    • 绝对误差限：${\epsilon }^{\ast }$$\ve^*$ 是 $e^{\ast }$$e^*$ 的上界.

  • 备注

    • 不等式简写：$x=x^{\ast }\pm {\epsilon }^{\ast }$$x = x^* \pm \ve^*$.

    • 一般写为：${\epsilon }^{\ast }=0.5\times {10}^{-n}$$\ve^* = 0.5 \cp 10^{-n}$.

  • 无量纲

    • 相对误差：$e_{\mathrm{r}}^{\ast }={\displaystyle \frac{e^{\ast }}{x}}$$e_\rm r^* = \dfrac{e^*}{x}$ 或 ${\displaystyle \frac{e^{\ast }}{x^{\ast }}}$$\dfrac{e^*}{x^*}$.

    • 相对误差限：${\epsilon }_{\mathrm{r}}^{\ast }={\displaystyle \frac{{\epsilon }^{\ast }}{\left|x^{\ast }\right|}}$$\ve_\rm r^* = \dfrac{\ve^*}{\vqty{x^*}}$.

• 有效数字

  • 对于 $x^{\ast }=\pm {10}^m\times (a_1+a_2\times {10}^{-1}+\cdots +a_l\times {10}^{-l-1})$$x^* = \pm 10^m \cp (a_1 + a_2 \cp 10\inv + \cdots + a_l \cp 10^{-{l-1}})$，

  • 若具有 $n$$n$ 位有效数字，则其相对误差限 ${\epsilon }_{\mathrm{r}}^{\ast }\le {\displaystyle \frac{1}{2a_1}}\times {10}^{-n-1}$$\ve_\rm r^* \le \dfrac{1}{2a_1} \cp 10^{-{n-1}}$.

  • 若相对误差限 ${\epsilon }_{\mathrm{r}}^{\ast }\le {\displaystyle \frac{1}{2(a_1+1)}}\times {10}^{-(n-1)}$$\ve_\rm r^* \le \dfrac{1}{2 (a_1 + 1)} \cp 10^{-(n-1)}$，则至少具有 $n$$n$ 位有效数字.

1.1.5 算法的稳定性

即计算过程中舍入误差不增长.

稳定性是计算方法引起的，而非数值问题自身固有.

1.1.6 问题的病态性

即输入数据的微小扰动引起输出数据相对误差很大的问题.

病态性是数值问题自身固有的，而非计算方法引起.

1.1.7 迭代法

• 求解 $\sqrt{a}$$\sqrt a$.

  • $x_{n+1}={\displaystyle \frac{1}{2}}(x_n+{\displaystyle \frac{a}{x_n}})$$x_{n+1} = \dfrac{1}{2} \pqty{x_n + \dfrac{a}{x_n}}$.

  • 一般 4~5 次迭代就能达到 ${10}^{-8}$$10^{-8}$ 的精度.

• 求解 $\sqrt[k]{a}$$\sqrt[k]a$.

  • $x_{n+1}={\displaystyle \frac{1}{k}}((k-1)x_n+{\displaystyle \frac{a}{x_n^{k-1}}})$$x_{n+1} = \dfrac{1}{k} \pqty{ (k - 1) x_n + \dfrac{a}{x_n^{k-1}} }$，或者说

    $x_{n+1}=x_n(1-{\displaystyle \frac{1}{k}}+{\displaystyle \frac{a}{k{x}_n^k}})$$x_{n+1} = x_n \pqty{1 - \dfrac{1}{k} + \dfrac{a}{k x_n^k}}$.

  • 上二式本质上是牛顿迭代法.

1.1.8 以直代曲

同 1.1.7 迭代法.

1.1.9 松弛法

松弛法：$\bar{a}=a_n+\omega (a_n-a_{n-1})$$\overline a = a_n + \omega (a_n - a_{n-1})$. 以复化求积公式为例，

• $T_1={\displaystyle \frac{x_1-x_0}{2}}[f(x_0)+f(x_1)]$$T_1 = \dfrac{x_1 - x_0}{2} \bqty{f(x_0) + f(x_1)}$.

• $T_2={\displaystyle \frac{x_2-x_0}{4}}[f(x_0)+2f(x_1)+f(x_2)]$$T_2 = \dfrac{x_2 - x_0}{4} \bqty{f(x_0) + 2f(x_1) + f(x_2)}$.

• $S_1=T_2+{\displaystyle \frac{T_2-T_1}{3}}={\displaystyle \frac{x_2-x_0}{6}}[f(x_0)+4f(x_1)+f(x_2)]$$S_1 = T_2 + \dfrac{T_2 - T_1}{3} = \dfrac{x_2 - x_0}{6} \bqty{f(x_0) + 4f(x_1) + f(x_2)}$.

1.10 无穷级数的和

一般来说，“大数吃小数”，最后稳定为常数.（除非软件可以自动调整精度）

1.11 一些命题

1. √.

2. ×，病态性是问题固有的.

3. ×，只有良态问题才能通过稳定的算法得到较好的近似值.

4. ×，还与初值有关.

5. ×，还与初值有关.

6. ×，可以通过其他方式避免有效数字的损失.

7. ×，可能存在大数吃小数的问题.

1.2 习题

1.2.1 函数的绝对误差

• 法一（由定义）$\epsilon (\ln x)=\ln x^{\ast }-\ln x=\ln (1+{\displaystyle \frac{x^{\ast }-x}{x}})\approx {\displaystyle \frac{x^{\ast }-x}{x}}=\delta$$\ve(\ln x) = \ln x^* - \ln x = \ln\pqty{1 + \dfrac{x^* - x}{x}} \approx \dfrac{x^* - x}{x} = \delta$.

• 法二（由公式）$\epsilon (\ln x)\approx {\displaystyle \frac{\mathrm{d}\ln x^{\ast }}{\mathrm{d}{x}^{\ast }}\epsilon (x)={\displaystyle \frac{\epsilon (x)}{x^{\ast }}}={\displaystyle \frac{x^{\ast }\delta }{x^{\ast }}}=\delta }$$\ve(\ln x) \approx \ddv{\ln x^*}{x^*} \ve(x) = \dfrac{\ve(x)}{x^*} = \dfrac{x^* \delta}{x^*} = \delta$.

备注 法二是法一的一般情况.

1.2.2 函数的相对误差

• 法一（由公式）${\epsilon }_{\mathrm{r}}(x^n)={\displaystyle \frac{\epsilon (x^n)}{x^n}}={\displaystyle \frac{n{x}^{n-1}\epsilon (x)}{x^n}}=n\delta$$\ve_\rm r(x^n) = \dfrac{\ve(x^n)}{x^n} = \dfrac{n x^{n-1} \ve(x)}{x^n} = n \delta$.

• 法二（条件数）$C_p=\left|{\displaystyle \frac{x{f}^{\prime }(x)}{f(x)}}\right|=n$$C_p = \vqty{\dfrac{x f'(x)}{f(x)}} = n$，${\epsilon }_{\mathrm{r}}(x^n)=n\delta$$\ve_\rm r(x^n) = n\delta$.

备注 法二是法一的一般情况.

1.2.3 数字的有效位数

1. 5 位.

2. 2 位.

3. 4 位.

4. 5 位.

5. 2 位.

1.2.4 多元函数误差限

1. 单变量的误差限

   1. $\epsilon (x_1^{\ast })={\displaystyle \frac{1}{2}}\times {10}^{-4}$$\ve(x_1^*) = \dfrac{1}{2} \cp 10^{-4}$.

   2. $\epsilon (x_2^{\ast })={\displaystyle \frac{1}{2}}\times {10}^{-3}$$\ve(x_2^*) = \dfrac{1}{2} \cp 10^{-3}$.

   3. $\epsilon (x_3^{\ast })={\displaystyle \frac{1}{2}}\times {10}^{-1}$$\ve(x_3^*) = \dfrac{1}{2} \cp 10^{-1}$.

   4. $\epsilon (x_4^{\ast })={\displaystyle \frac{1}{2}}\times {10}^{-3}$$\ve(x_4^*) = \dfrac{1}{2} \cp 10^{-3}$.

2. 表达式的误差限

   1. $\epsilon (y_1)=1.05\times {10}^{-4}\approx {\displaystyle \frac{1}{2}}\times {10}^{-3}$$\ve(y_1) = 1.05 \cp 10^{-4} \approx \dfrac{1}{2} \cp 10^{-3}$.

   2. $\epsilon (y_2)\approx \left|x_1^{\ast }{x}_2^{\ast }{x}_3^{\ast }\right|({\displaystyle \frac{\epsilon (x_1^{\ast })}{x_1^{\ast }}}+{\displaystyle \frac{\epsilon (x_2^{\ast })}{x_2^{\ast }}}+{\displaystyle \frac{\epsilon (x_3^{\ast })}{x_3^{\ast }}})\approx 0.21479\approx {\displaystyle \frac{1}{2}}\times {10}^{-1}$$\ve(y_2) \approx \vqty{x_1^* x_2^* x_3^*} \pqty{\dfrac{\ve(x_1^*)}{x_1^*} + \dfrac{\ve(x_2^*)}{x_2^*} + \dfrac{\ve(x_3^*)}{x_3^*}} \approx 0.21479 \approx \dfrac{1}{2} \cp 10^{-1}$.

   3. $\epsilon (y_3)\approx {\displaystyle \frac{\left|x_2^{\ast }\right|\epsilon (x_4^{\ast })+\left|x_4^{\ast }\right|\epsilon (x_2^{\ast })}{{\left|x_4^{\ast }\right|}^2}}\approx 0.8865\times {10}^{-5}\approx {\displaystyle \frac{1}{2}}\times {10}^{-4}$$\ve(y_3) \approx \dfrac{\vqty{x_2^*} \ve(x_4^*) + \vqty{x_4^*} \ve(x_2^*)}{\vqty{x_4^*}^2} \approx 0.8865 \cp 10^{-5} \approx \dfrac{1}{2} \cp 10^{-4}$.

1.2.5 函数相对误差限

$V={\displaystyle \frac{4}{3}}\pi R^3$$V = \dfrac{4}{3} \pi R^3$，$C_p=\left|{\displaystyle \frac{R\cdot 4\pi R^2}{\frac{4}{3}\pi R^3}}\right|=3$$C_p = \vqty{\dfrac{R \cdot 4 \pi R^2}{\cfrac{4}{3} \pi R^3}} = 3$.

${\epsilon }_{\mathrm{r}}(R^{\ast })={\displaystyle \frac{1}{C_p}}=0.33\mathrm{\%}$$\ver(R^*) = \dfrac{1}{C_p} = 0.33\%$.

1.2.6 递推公式的误差

$Y_n=Y_0-{\displaystyle \frac{n}{100}}\sqrt{783}$$Y_n = Y_0 - \dfrac{n}{100} \sqrt{783}$，

$Y_{100}^{\ast }=Y_0-\sqrt{783}=0.018$$Y_{100}^* = Y_0 - \sqrt{783} = 0.018$，

$\epsilon (Y_{100}^{\ast })={\displaystyle \frac{1}{2}}\times {10}^{-3}$$\ve(Y_{100}^*) = \dfrac{1}{2} \cp 10^{-3}$.

1.2.7 按有效数字求解

$x_{1,2}=28\pm \sqrt{783}$$x_{1, 2} = 28 \pm \sqrt{783}$，

$x_1^{\ast }=28+\sqrt{783}\approx 55.982$$x_1^* = 28 + \sqrt{783} \approx 55.982$，舍入误差 $\epsilon (x_1^{\ast })={\displaystyle \frac{1}{2}}\times {10}^{-3}$$\ve(x_1^*) = \dfrac{1}{2} \cp 10^{-3}$，故具有 5 位有效数字.

$x_2^{\ast }={\displaystyle \frac{1}{28+\sqrt{783}}}\approx 0.017863$$x_2^* = \dfrac{1}{28 + \sqrt{783}} \approx 0.017863$，舍入误差 $\epsilon (x_2^{\ast })=0.160\times {10}^{-6}$$\ve(x_2^*) = 0.160 \cp 10^{-6}$，故具有 5 位有效数字.

备注

• 实际上 $x_1^{\ast }$$x_1^*$ 的表达式中应将根号替换为小数，不过那样麻烦也不直观.

• 注意该题首先需要从理论上证明舍入误差可以足够小，否则后续计算是没有意义的.

1.2.8 舍入误差的减少

对于 $f(x)=\ln x$$f(x) = \ln x$，$C_p=\left|{\displaystyle \frac{x{f}^{\prime }(x)}{f(x)}}\right|=\left|{\displaystyle \frac{1}{\ln x}}\right|$$C_p = \vqty{\dfrac{x f'(x)}{f(x)}} = \vqty{\dfrac{1}{\ln x}}$，

故 $x\approx y$$x \approx y$ 时 $C_0$$C_0$ 充分大，是病态问题，这样做不能减少相对误差，但是可以减少绝对误差.

1.2.9 函数误差的控制

$S=a^2$$S = a^2$，$\epsilon (S^{\ast })=2a^{\ast }\epsilon (a^{\ast })$$\ve(S^*) = 2a^* \ve(a^*)$，

$\epsilon (a^{\ast })\le {\displaystyle \frac{\epsilon (S^{\ast })}{2a^{\ast }}}\approx {\displaystyle \frac{1}{2}}\times {10}^{-2}$$\ve(a^*) \le \dfrac{\ve(S^*)}{2a^*} \approx \dfrac{1}{2} \cp 10^{-2}$.

1.2.10 误差的变化趋势

$\epsilon (S^{\ast })=g{t}^{\ast }\epsilon (t^{\ast })$$\ve(S^*) = gt^* \ve(t^*)$，故 $t$$t$ 增加时 $S$$S$ 的绝对误差增加.

$C_p=2$$C_p = 2$，${\epsilon }_{\mathrm{r}}(S^{\ast })=2{\epsilon }_{\mathrm{r}}(t^{\ast })={\displaystyle \frac{2\epsilon (t)}{t}}$$\ver(S^*) = 2 \ver(t^*) = \dfrac{2 \ve(t)}{t}$，故 $t$$t$ 增加时 $S$$S$ 的相对误差减小.

1.2.11 算法数值稳定性

$\epsilon (y_n^{\ast })=10\epsilon (y_{n-1}^{\ast })$$\ve(y_n^*) = 10 \ve(y_{n-1}^*)$，故 $\epsilon (y_{10}^{\ast })={10}^{10}\times {\displaystyle \frac{1}{2}}\times {10}^{-2}={\displaystyle \frac{1}{2}}\times {10}^8$$\ve(y_{10}^*) = 10^{10} \cp \dfrac{1}{2} \cp 10^{-2} = \dfrac{1}{2} \cp 10^8$，

舍入误差逐渐增大，故计算过程不稳定.

1.2.12 计算方法的优劣

1. $\epsilon (f_1^{\ast })=0.013\epsilon (x^{\ast })$$\ve(f_1^*) = 0.013 \ve(x^*)$.

2. $\epsilon (f_2^{\ast })=0.24\epsilon (x^{\ast })$$\ve(f_2^*) = 0.24 \ve(x^*)$.

3. $\epsilon (f_3^{\ast })=0.0053\epsilon (x^{\ast })$$\ve(f_3^*) = 0.0053 \ve(x^*)$.

4. $\epsilon (f_4^{\ast })=70\epsilon (x^{\ast })$$\ve(f_4^*) = 70 \ve(x^*)$.

故第三种方法好.

1.2.13 绝对误差的减小

0. 有效位数为 6 位函数表中，$\sqrt{{30}^2-1}\approx 29.9833$$\sqrt{30^2 - 1} \approx 29.9833$.

1. $\epsilon (f_1^{\ast })={\displaystyle \frac{\frac{1}{2}\times {10}^{-4}}{30-\sqrt{899}}}=0.00299(\approx {\displaystyle \frac{1}{2}}\times {10}^{-2})$$\ve(f_1^*) = \dfrac{\cfrac{1}{2} \cp 10^{-4}}{30 - \sqrt{899}} = 0.00299 \pqty{\approx \dfrac{1}{2} \cp 10^{-2}}$.

2. $\epsilon (f_2^{\ast })=0.834\times {10}^{-6}$$\ve(f_2^*) = 0.834 \cp 10^{-6}$.

故第二种方法误差较小.

备注 虽然习惯上将误差限表示为 ${\displaystyle \frac{1}{2}}\times {10}^{-n}$$\dfrac{1}{2} \cp 10^{-n}$，但是这样不利于理论推导，而仅仅在实践应用上方便.

1.2.14 秦九韶算法求值

$p(x)=((3x^2-2)x^2+1)x+7$$p(x) = ((3x^2 - 2) x^2 + 1) x + 7$，$p(3)=685$$p(3) = 685$.

代码略.

1.2.15 迭代法求方程根

1
f[x_] := Which[
2
    x == 0, 1,
3
    x > 0,  1/(1 + f[x - 1])
4
];
5
N[f[5]]
6
Abs[% - (Sqrt[5] - 1)/2]

由计算机得 $x_5={\displaystyle \frac{8}{13}}=0.615385$$x_5 = \dfrac{8}{13} = 0.615385$，误差为 $0.00265$$0.00265$，故有两位有效数字.

1.2.16 复化求积松弛法

1. $f^{\ast }={\mathrm{e}}^{\frac{1}{2}}-1\approx 0.648721$$f^* = \e^{\tfrac{1}{2}} - 1 \approx 0.648721$.

2. $f^{\ast }={\displaystyle \frac{{\mathrm{e}}^0+2{\mathrm{e}}^{1/4}+{\mathrm{e}}^{1/2}}{8}}\approx 0.652096$$f^* = \dfrac{\e^0 + 2 \e^{1/4} + \e^{1/2}}{8} \approx 0.652096$.

3. $T_1={\displaystyle \frac{{\mathrm{e}}^0+{\mathrm{e}}^{1/2}}{4}}=0.662180$$T_1 = \dfrac{\e^0 + \e^{1/2}}{4} = 0.662180$,

   $T_2=0.652096$$T_2 = 0.652096$.

   $S_1={\displaystyle \frac{4}{3}}{T}_2-{\displaystyle \frac{1}{3}}{T}_1=0.648735$$S_1 = \dfrac{4}{3} T_2 - \dfrac{1}{3} T_1 = 0.648735$.

1.2.17 迭代公式的改善

xxxxxxxxxx
6
1
g[x_] := Which[
2
    x == 0, 1,
3
    x > 0, 7/25 g[x - 1] + 18/(25 (1 + g[x - 1]))
4
];
5
N[g[3]]
6
Abs[% - (Sqrt[5] - 1)/2]

由计算机得 $x_3=0.618035$$x_3 = 0.618035$，误差为 $9.55\times {10}^{-7}$$9.55 \cp 10^{-7}$，故有 5 位有效数字，已经比 15 题计算 5 次的精度高许多了.